package try01;

public class editDistance {
	public void tester() {
		String w1 = "adsfafasgfhkhifduhaiufhakjsaduifhsadkjfkjashfkasdfhasfklhaksldfh";
		String w2 = "hklahsfkhkaghaskdfksalgahsdfjklajsdlkfkjhakgjhsadkfhkalsdjfhaksd";
		System.out.println(minDistance_recursionCache(w1,w2));
	}
	
	
	public int minDistance_recursionCache(String w1, String w2) {
		cache = new int [w1.length()][w2.length()];
		for(int i =0 ; i < w1.length(); i++) {
			for(int j = 0 ; j < w2.length(); j++) {
				cache[i][j] = -1;
			}
		}
		return md(w1, 0, w2, 0);
	}
	
	int [][] cache;
	public int md(String w1, int s1, String w2, int s2) {
		if(w1.length() == 0 || s1 >= w1.length()) return w2.length() - s2;
		if(w2.length() == 0 || s2 >= w2.length()) return w1.length() - s1;
		
		if(cache[s1][s2] != -1) return cache[s1][s2];
		
		int min = Integer.MAX_VALUE;
		
		if(w1.charAt(s1) == w2.charAt(s2)) {
			int t = md(w1, s1+1, w2, s2+1);
			if(t < min) min = t;
		}
		
		int t = 1 + md(w1, s1, w2, s2+1);
		if(t < min) min = t;
		
		t = 1 + md(w1, s1+1, w2, s2);
		if(t < min) min = t;
		
		t = 1 + md(w1, s1+1, w2, s2+1);
		if(t < min) min = t;
		
		cache[s1][s2] = min;
		return min;
	}
	
	public int minDistance_greedy(String w1, String w2) {
		int min = Integer.MAX_VALUE;
		
		for(int i = w2.length() ; i >= 1; i--) { // window size
			for(int j = 0 ; j <= w2.length() - i; j++) { // w2
				for(int k = 0 ; k <= w1.length() - i ; k++) { // w1
					String w1n = w1.substring(k, k+i);
					String w2n = w2.substring(j, j+i);
					
					if(w1n.equals(w2n)) {
						String w1a = w1.substring(0, k);
						String w2a = w2.substring(0, j);
						
						String w1b = w1.substring(k+i);
						String w2b = w2.substring(j+i);
						
						int temp = minDistance_greedy(w1a, w2a) + minDistance_greedy(w1b, w2b);
						
						if(min > temp) min = temp;
					}
				}
			}
			if(min != Integer.MAX_VALUE) break;
		}
		
		int w1l = w1.length();
		int w2l = w2.length();
		
		if(w1l > w2l) {
			if(min > w1l) min = w1l;
		}
		else {
			if(min > w2l) min = w2l;
		}
		
		return min;
    }
	
	public int minDistance_textbookSolution(String word1, String word2) {
	    if (word1.equals(word2)) {
	        return 0;
	    }
	    if (word1.length() == 0 || word2.length() == 0) {
	        return Math.abs(word1.length() - word2.length());
	    }
	    int[][] dp = new int[word1.length() + 1][word2.length() + 1];
	    for (int i = 0; i <= word1.length(); i++) {
	        dp[i][0] = i;
	    }
	    for (int i = 0; i <= word2.length(); i++) {
	        dp[0][i] = i;
	    }
	    for (int i = 1; i <= word1.length(); i++) {
	        for (int j = 1; j <= word2.length(); j++) {
	            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
	                dp[i][j] = dp[i - 1][j - 1];
	            } else {
	                dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
	            }
	        }
	    }
	    return dp[word1.length()][word2.length()];
	}
	
	
	
    public int minDistance_recursion(String word1, String word2) {
        md(word1, word2, 0);
        System.out.println("count: "+cc);
        return min;
    }
    
    int min = Integer.MAX_VALUE;
    long cc = 0;
    
    public void md(String w1, String w2, int count) {
    	cc++;
//    	System.out.println(count+" "+w1+" "+w2);
    	if(count > min) return;
        if(w1.equals(w2)) {
            if(min > count) min = count;
            return;
        }
        
        for(int i =0 ; i < w1.length() && i < w2.length() ; i++) {
            if(w1.charAt(i) != w2.charAt(i)) {
            	md(insert(w1, i, w2.charAt(i)), w2, count+1);
            	md(remove(w1, i), w2, count+1);
            	md(replace(w1, i, w2.charAt(i)), w2, count+1);
            	return;
            }
        }
        
        while(w1.length() > w2.length()) {
        	w1 = remove(w1, w2.length());
        	count++;
        	if(w1.equals(w2)) {
                if(min > count) min = count;
                return;
            }
        }
        while(w1.length() < w2.length()) {
        	w1 = insert(w1, w1.length(), w2.charAt(w1.length()));
        	count++;
        	if(w1.equals(w2)) {
                if(min > count) min = count;
                return;
            }
        }
    }
    
    public String insert(String str, int i, char r) {
        if(i == 0) {
            return ""+r+str.substring(0);
        }
        if(i == str.length() - 1) {
            return str.substring(0, i+1)+r;
        }
        return str.substring(0, i) + r + str.substring(i, str.length());
    }
    
    public String replace(String str, int i, char r) {
        if(i == 0) {
            return ""+r+str.substring(1);
        }
        if(i == str.length() - 1) {
            return str.substring(0, i)+r;
        }
        return str.substring(0, i) + r + str.substring(i+1, str.length());
    }
    
    public String remove(String str, int i) {
        if(i == 0) {
            return str.substring(1);
        }
        if(i == str.length() - 1) {
            return str.substring(0, i);
        }
        return str.substring(0, i) + str.substring(i+1, str.length());
    }
}